package 题目集.扫描线;

import org.junit.Test;

import java.util.*;

/**
 * https://leetcode.cn/problems/the-skyline-problem/description/
 */
public class ch02_天际线 {
    /**
     * 扫描线：
     *      先对所有建筑按左端点进行排序
     *      把所有的端点放入一个有序集合中，作为扫描线
     *      对于每一个扫描线，将左端点小于等于当前扫描线的建筑放入一个大根堆中，堆中存储高度和右端点
     *      对于每一个扫描线，取出左端点在扫描线左侧，右端点在扫描线右侧的最高建筑。
     *      由于扫描线中可能出现无用的端点。所以需要一个标记来记录上一个端点的高度，如果高度不同，就加入结果集
     */
    PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> b[0] - a[0]);    //存储高度和右端点,高的在前

    public List<List<Integer>> getSkyline(int[][] buildings) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(buildings, (a, b) -> {
            if (a[0] != b[0]) {
                return a[0] - b[0];
            } else {
                return a[1] - b[1];
            }
        });
        TreeSet<Integer> treeSet = new TreeSet<>();  //用于存储扫描线的点
        for (int[] curr : buildings) {
            treeSet.add(curr[0]);
            treeSet.add(curr[1]);
        }
        int i = 0;
        List<Integer> last=new ArrayList<Integer>(){{
            add(0);
            add(-1);
        }};
        for (Integer cur : treeSet) {
            //将左端点小于=当前扫描线的建筑弹出
            while (i < buildings.length && buildings[i][0] <= cur) {
                int[] info = {buildings[i][2], buildings[i][1]};
                queue.add(info);
                i++;
            }
            //取出左端点在扫描线左侧，右端点在扫描线右侧的最高建筑
            List<Integer> height = height(cur);
            if (!last.get(1).equals(height.get(1))){
                result.add(height);
                last=height;
            }
        }
        return result;
    }

    public List<Integer> height(int v) {
        List<Integer> list = new ArrayList<>();
        list.add(v);
        //将右端点比自己小的区间弹出
        while (!queue.isEmpty() && queue.peek()[1] <= v) {
            queue.poll();
        }
        list.add(queue.isEmpty() ? 0 : queue.peek()[0]);
        return list;
    }

    @Test
    public void test() {
        int[][] buildings = {{2, 9, 10}, {3, 7, 15}, {5, 12, 12}, {15, 20, 10}, {19, 24, 8}};
        List<List<Integer>> skyline = getSkyline(buildings);
        System.out.println(skyline);
    }
}
